This invention relates to cache logic for generating a cache address, to a cache memory system and to a method for generating a cache address.
Cache memories are widely used to increase the performance of data processing systems by reducing the latency associated with memory accesses. This is generally achieved by caching some previously accessed (e.g. the most recently accessed) data at a cache memory which can be accessed at a lower latency than the main memory in which the data is stored. In order to ensure that cached data can be readily retrieved from the cache memory, the cached data must be organised according to a defined scheme.
Typically the data for caching is held at a resource identified by an address, such as a memory address, or a hardware resource address in a computing system. The access of such resource addresses can follow certain fixed patterns (such as accesses of sequential memory blocks), and care may therefore be taken to ensure that data representing related (e.g. sequential) resource addresses are well-distributed over the cache memory so as to avoid pathological access cases. A sequence of addresses that all map to only a few cache lines is an example of a pathological access case, in which repeatedly accessing the same few cache lines may lead to a significant number of cache line replacements and a poor hit rate when data is required from the cache. Such behaviour severely affects the performance of a cache memory.
Several mechanisms have been proposed in the art for improving the distribution of data over a cache and maximising the cache hit rate for a given size of cache. These mechanisms may use hash functions to inject pseudorandom variation into the mapping of data onto cache addresses. For example, M. Schlansker et al. describe the use of a hash function to randomise the placement of data in a cache in their paper “Randomization and Associativity in the Design of Placement-Insensitive Caches”, Computer Systems Laboratory, HPL-93-41, June 1993. However, the use of such complex hash functions is generally too expensive in terms of silicon area and latency to be implemented in the critical path of a high speed cache memory system.
Other mechanisms for improving cache performance by avoiding cache access collisions (e.g. which may occur when cached data cannot be accessed because another cache read is being performed on the same cache line) include using a skewed-associative cache architecture. Such architectures are described in “A case for two-way skewed-associative caches”, A. Seznec, Proceedings of the 20th International Symposium on Computer Architecture, San Diego, May 1993 and in “Trade-offs for Skewed-Associative Caches”, H. Vandierendonck and K. De Bosschere (a paper published by Dept. of Electronics and Information Systems, Ghent University). Skewed-associative architectures require multiple cache banks because the mechanism achieves low miss rates through inter-bank dispersion of cache addresses. However, as is observed in the Vandierendonck paper, the best performance is achieved by combining a skewed-associative architecture with hash functions to inject random character into the mapping of data into the cache. Again, such hash functions are complex and generally too expensive to implement in the critical path of a high speed cache memory system.